package com.yiguang.algorithm.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BinaryTree {
	
	public static void main(String[] args) {
		TreeNode wu = new TreeNode(5);
		TreeNode er = new TreeNode(2, null, wu);
		TreeNode si = new TreeNode(4);
		TreeNode san = new TreeNode(3, null, si);
		TreeNode yi = new TreeNode(1, er, san);
		
		/*
		 *      1
		 *   2		3
		 *    5 	 4
		 */
		System.out.println(rightSideView(yi));
	}

	/* 广度优先搜素例题
	102. 二叉树的层序遍历
	给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
	*/
	public List<List<Integer>> levelOrder(TreeNode root) {
		List<List<Integer>> result = new ArrayList();
		Queue<TreeNode> queue = new LinkedList();
		if(root==null) {
			return result;
		}
		queue.offer(root);
		while(!queue.isEmpty()) {
			List<Integer> temp = new ArrayList();
			int currentLevelSize = queue.size();
			for(int i=0; i<currentLevelSize; i++) {
				TreeNode current = queue.poll();
				temp.add(current.val);
				if(current.left!=null) {
					queue.offer(current.left);
				}
				if(current.right!=null) {
					queue.offer(current.right);
				}
			}
			result.add(temp);
			
		}
		return result;

    }
	
	/*
	 * 199. 二叉树的右视图
		给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
	 */
	public static List<Integer> rightSideView(TreeNode root) {
		List<Integer> result = new ArrayList();
        if(root==null) {
        	return result;
        }
        Queue<TreeNode> queue = new LinkedList();
        Queue<TreeNode> tempQueue = new LinkedList();
        queue.offer(root);
        while(!queue.isEmpty()) {
        	TreeNode currentNode = queue.poll();
        	if(currentNode.left!=null) {
        		tempQueue.offer(currentNode.left);
        	}
        	if(currentNode.right!=null) {
        		tempQueue.offer(currentNode.right);
        	}
        	if(queue.isEmpty()) {
        		result.add(currentNode.val);
        		// 深度拷贝
        		queue = new LinkedList(tempQueue);
        		// 临时队列清空
        		tempQueue.clear();
        	}
        }
        return result;
    }
}

/**
 * Definition for a binary tree node.
 */
 class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode() {}
     TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }
}
